#include "get_lcs.h"
#include <iostream>
#include <string> 
#include <cstdlib> 
#include <cstdio> 
#include <vector>
#include <stdexcept>

using namespace std;
const unsigned int MAX_SEQUENCE_LENGTH = 1000;
const unsigned int MAX_STRING_LENGTH = 3;

int get_lcs_length(const vector<string>& first_sequence, const vector<string>& second_sequence) {
	vector<vector<int> > last_columns(2);
	for (int i = 0; i <= (int)second_sequence.size(); i++){
		last_columns[0].push_back(0);
		last_columns[1].push_back(0);
	}

	for (int i = 0; i<(int)first_sequence.size(); i++){
		for (int j = 0; j<(int)second_sequence.size(); j++){
			if (first_sequence[i] == second_sequence[j])
				last_columns[(i + 1) % 2][j + 1] = last_columns[i % 2][j] + 1;
			else
				last_columns[(i + 1) % 2][j + 1] = max(last_columns[i % 2][j + 1], last_columns[(i + 1) % 2][j]);
		}
	}
	return(last_columns[(int)first_sequence.size() % 2][(int)second_sequence.size()]);
}

bool is_subsequence(const vector<string>& subsequence, const vector<string>& sequence) {
	size_t subs_pointer = 0;
	for (size_t i = 0; i < sequence.size(); i++) {
		if (subs_pointer == subsequence.size())
			return true;
		if (subsequence[subs_pointer] == sequence[i])
			subs_pointer++;
	}
	return subs_pointer == subsequence.size();
}

bool is_lcs(const vector<string>& first_sequence, const vector<string>& second_sequence, const vector<string>& lcs) {
	int lcs_length = get_lcs_length(first_sequence, second_sequence);
	if (lcs_length != (int)lcs.size()) {
		return false;
	}
	return is_subsequence(lcs, first_sequence) && is_subsequence(lcs, second_sequence);
}

void test_lcs() {
	vector<string> first_sequence;
	vector<string> second_sequence;
	vector<string> lcs;
	//first test
	first_sequence.push_back("a");
	lcs = get_lcs_string(first_sequence, second_sequence);
	if (!is_lcs(first_sequence, second_sequence, lcs)) {
		throw logic_error("test_gcd: FAIL");
	}
	first_sequence.clear();
	second_sequence.clear();
	//second test
	first_sequence.push_back("a");
	second_sequence.push_back("a");
	lcs = get_lcs_string(first_sequence, second_sequence);
	if (!is_lcs(first_sequence, second_sequence, lcs)) {
		throw logic_error("test_gcd: FAIL");
	}
	first_sequence.clear();
	second_sequence.clear();
	//third test
	second_sequence.push_back("a");
	lcs = get_lcs_string(first_sequence, second_sequence);
	if (!is_lcs(first_sequence, second_sequence, lcs)) {
		throw logic_error("test_gcd: FAIL");
	}
	first_sequence.clear();
	second_sequence.clear();
	//fourth test
	lcs = get_lcs_string(first_sequence, second_sequence);
	if (!is_lcs(first_sequence, second_sequence, lcs)) {
		throw logic_error("test_gcd: FAIL");
	}
	first_sequence.clear();
	second_sequence.clear();
}

string get_random_string() {
	string result = "";
	int length = rand() % MAX_STRING_LENGTH + 1;
	for (int i = 0; i < length; i++) {
		result += (char)(rand() % 26 + int('a'));
	}
	return result;
}

vector<string> get_random_array() {
	vector<string> result;
	int size = rand() % MAX_SEQUENCE_LENGTH + 1;
	for (int i = 0; i < size; ++i) {
		result.push_back(get_random_string());
	}
	return result;
}

void test_lcs_random() {
	for (int case_no = 0; case_no < 1000; ++case_no) {
		vector<string> first_sequence;
		vector<string> second_sequence;
		vector<string> lcs;

		first_sequence = get_random_array();
		second_sequence = get_random_array();

		lcs = get_lcs_string(first_sequence, second_sequence);
		if (!is_lcs(first_sequence, second_sequence, lcs)) {
			throw logic_error("test_gcd: FAIL");
		}

		cout << "CASE:" << case_no << " OK" << endl;
	}
}


int main() {
	try {
		test_lcs();
		test_lcs_random();
	}
	catch (const std::exception& ex) {
		cerr << "Exception: " << ex.what() << endl;
		return -1;
	}
	return 0;
}
